package algorithm.t202110;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/24 8:56
 * @description :7道
 * 时间在走。
 * persevere to last
 * 2021.10.24
 */
public class t20211024 {


    //190.颠倒二进制位
    public int reverseBits(int n) {

        int res = 0;

        for (int i = 0; i < 32; i++) {

            res = (res << 1) | (n & (1 << i));

        }

        return res;
    }

    //136.只出现一次的数字
    public int singleNumber(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }


        for (int i = 1; i < nums.length; i++) {
            nums[0] = nums[0] ^ nums[i];
        }

        return nums[0];

    }

    //面试题08.01 三步问题
    public int waysToStep(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else if (n == 3) {
            return 4;
        }

        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for (int i = 4; i <= n; i++) {
            dp[i] = (dp[i - 1] + (dp[i - 2] + dp[i - 3]) % 1000000007) % 1000000007;

        }

        return (int) dp[n];

    }

    //面试题08.02 迷路的机器人
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        int rows = obstacleGrid.length, cols = obstacleGrid[0].length;
        if (obstacleGrid == null) {
            return res;
        }
        if (rows == 0) {
            return res;
        }
        if (obstacleGrid[rows - 1][cols - 1] == 1) {  // 终点有障碍
            return res;
        }

        boolean[][] visit = new boolean[rows][cols];

        dfs(obstacleGrid, 0, 0, res, visit);


        if (obstacleGrid[rows - 1][cols - 1] == 0) {
            res.clear();
            return res;
        }

        return res;
    }

    private boolean dfs(int[][] matrix, int x, int y, ArrayList<List<Integer>> res, boolean[][] visit) {
        if (x < 0 || x > matrix.length - 1 || y < 0 || y > matrix[0].length - 1 || matrix[x][y] == 1 || visit[x][y]) {
            return false;
        }

        res.add(Arrays.asList(x, y));
        visit[x][y] = true;

        //判断一下当前是否已经走到重点了
        if (x == matrix.length - 1 && y == matrix[0].length - 1) {
            return true;
        }


        //没有走到终点就继续走
        if (dfs(matrix, x, y + 1, res, visit) || dfs(matrix, x + 1, y, res, visit)) {
            return true;
        }

        res.remove(res.size() - 1);
        return false;

    }

    //面试题08.03 魔术索引
    public int findMagicIndex(int[] nums) {
        if (nums == null) {
            return -1;
        }
        //HashMap<Integer, Integer> map = new HashMap<>();

        //遍历数组，将“魔术索引”放入哈希表
        for (int i = 0; i < nums.length; i++) {
            if (i == nums[i]) {

                return i;
            }

        }
       /* //若哈希表长度为0，表面这个数组并不存在“魔术索引”
        if(map.isEmpty()){
            return -1;
        }


        //遍历哈希表，找到索引值最小的“魔术索引“
        Set<Integer> keySet = map.keySet();*/

        return -1;

    }

    public int findMagicIndex2(int[] nums) {
        int flag = 0;

        while (flag < nums.length) {
            if (nums[flag] == flag) {
                return flag;
            } else if (nums[flag] > flag) {
                flag = nums[flag];
            } else {
                flag++;//value小于flag
            }
        }

        return -1;
    }


    //面试题08.04 幂集
    public List<List<Integer>> subsets(int[] nums) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        if (nums == null) {
            return res;
        } else if (nums.length == 1) {
            res.add(new ArrayList<>());
            res.add(Arrays.asList(nums[0]));
            return res;
        }

        res.add(new ArrayList<>());//任何集合的子集都包含空集

        for (int number : nums) {
            //每遍历出来一个元素，就将这个元素追加到之前子集中从而构建成一个个新的子集
            for (int i = 0, j = res.size(); i < j; i++) {
                List<Integer> son = res.get(i);
                ArrayList<Integer> newSon = new ArrayList<>(son);
                newSon.add(number);//
                res.add(newSon);

            }
        }

        return res;
    }


    //34.在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        if (nums == null) {
            return new int[]{-1, -1};
        } else if (nums.length == 0)  {
            return new int[]{-1,-1};
        }


        int first = findFirstIndex(nums, target);
        if (first == -1) {//表示该数组中不存在目标元素
            return new int[]{-1, -1};
        }
        //开始查询目标元素最后一次出现的位置
        int end = findEndIndex(nums, target);


        return new int[]{first, end};
    }
    private int findEndIndex(int[] nums, int target) {//查找目标元素最后一次出现的位置
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right >>> 1) + 1;
            if (nums[mid] == target) {
                //向右边去继续查找
                left = mid;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }

        }
        if (nums[right] == target) {//查询结束后，若一切正常，right指向的应该是目标元素最后一次出现的位置
            return right;
        } else {
            return -1;
        }
    }
    private int findFirstIndex(int[] nums, int target) {//查找目标元素第一次出现的位置
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + right >>> 1;
            if (nums[mid] == target) {
                //走到这里，说明mid之后的下标都不可能是目标元素一次出现的位置。 所以我们向左缩小查询范围
                right = mid;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (nums[left] == target) {
            return left;
        } else {
            return -1;
        }
    }


    public static void main(String[] args) {
        t20211024 t20211024 = new t20211024();

        t20211024.waysToStep(5);

        /*int[][] matrix = new int[4][5];
        matrix[0][0] = 0;
        matrix[0][1] = 0;
        matrix[0][2] = 0;
        matrix[0][3] = 0;
        matrix[0][4] = 0;

        matrix[1][0] = 0;
        matrix[1][1] = 0;
        matrix[1][2] = 0;
        matrix[1][3] = 0;
        matrix[1][4] = 1;

        matrix[2][0] = 0;
        matrix[2][1] = 0;
        matrix[2][2] = 0;
        matrix[2][3] = 1;
        matrix[2][4] = 0;

        matrix[3][0] = 0;
        matrix[3][1] = 0;
        matrix[3][2] = 0;
        matrix[3][3] = 0;
        matrix[3][4] = 0;*/

        System.out.println(t20211024.findMagicIndex(new int[]{1, 1, 1}));


    }


}
